package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/problems/predict-the-winner/comments/
 * @author: STU756
 * @create: 2020-09-02 00:03
 */
public class Pro0486 {
    public boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for(int n : nums) {
            sum += n;
        }
        int len = nums.length;
        int[][] f = new int[len][len];
        for(int i = 0; i < len; i++) {
            f[i][i] = nums[i];
        }
        for(int i = 1; i < len; i++) {
            f[i-1][i] = Math.max(nums[i-1], nums[i]);
        }
        for(int i = 2; i < len; i++) {
            for(int j = 0; j + i < len; j++) {
                f[j][j+i] = Math.max(nums[j] + Math.min(f[j+1][i+j-1], f[j+2][i+j]),   //1 5 2  玩家1如果选了1的时候，玩家二可能会选5 或者2
                        nums[i+j] + Math.min(f[j][i+j-2], f[j+1][i+j-1]));   //同理
            }
        }
        return f[0][len-1] * 2 >= sum;
    }
}
